#include "linearList.h"

// 添加构造函数和析构函数
sequenceList::sequenceList(const int& maxCapcity, const int& curNumberOfItem, float myList[]){
    this->maxCapcity = maxCapcity;
    this->curNumberOfItem = curNumberOfItem;
    this->myList = new float[maxCapcity];
    for(int i = 0; i < curNumberOfItem; i++){
        this->myList[i] = myList[i];
    }
}

sequenceList::~sequenceList(){

}

//顺序表打印
void sequenceList::print()
{
    cout << curNumberOfItem << ":";

    for(int i = 0; i < curNumberOfItem-1; i++)
    {
        cout << myList[i] << ",";
    }

    cout << myList[curNumberOfItem-1] << endl;
}

//TODO

//顺序表添加元素
bool sequenceList::addItem(const float& val){
    if(this->curNumberOfItem == this->maxCapcity)return false;
    this->myList[curNumberOfItem] = val;
    this->curNumberOfItem ++;
    return true;
}

//插入元素
bool sequenceList::insertItem(const int& index, const float& val)//插入元素到index位置，成功返回true，失败返回false
{
    // 判断是否超出范围；是否已达到最大容量
    if (index < 0 or index > curNumberOfItem)
    {
        return false;
    }
    if (curNumberOfItem == maxCapcity)
    {
        return false;
    }
    // 向后移动元素
    for (int i = curNumberOfItem; i > index; i --)
    {
        myList[i] = myList[ i - 1];
    }
    // 插入新元素；更新元素数量
    myList[index] = val;
    curNumberOfItem ++;
    return true;
}


//删除元素
int sequenceList::deleteItem(const float& val)//返回删除位置，找不到返回-1
{
    int index = -1;
    for(int i = 0; i < curNumberOfItem; i++){
        if(this->myList[i] == val){
            for(int j = i; j < curNumberOfItem - 1; j++){
                this->myList[j] = this->myList[j + 1];
            }
            index = i;
            this->curNumberOfItem--;
            break;
        }
    }
    
    return index;
}

//查找元素（按序号找）
bool sequenceList::locate(const int& index, float& val)// 成功返回true，值放在val中，失败返回false
{
    if(index >= curNumberOfItem || index < 0)return false;
    val = this->myList[index];
    return true;
}

//查找元素（按值找）
int sequenceList::locate(const float& val)//返回找到位置，找不到返回-1
{
    for(int i = 0; i < curNumberOfItem; i++){
        if(this->myList[i] == val){
            return i;
        }
    }
    return -1;
}

//倒序排列元素（使用原空间）
void sequenceList::reverse(){
    int left = 0;
    int right = curNumberOfItem - 1;
    while (left < right)
    {
        // 交换左右两个元素
        float temp = myList[left];
        myList[left] = myList[right];
        myList[right] = temp;
        // 左右边界向内移动一位
        left++;
        right--;
    }
}







//------------------------------------------------------



//链表打印
void linkList::print()
{
    curNode = firstNode;

    cout << listSize << ":";

    while(curNode != lastNode)
    {
        if(curNode->next == lastNode)
            cout << curNode->next->data << endl;
        else
        {
            cout << curNode->next->data << ",";
        }
        
        
        curNode = curNode->next;
    }
}


//TODO
//初始化节点
listNode::listNode(float nodeData, listNode* succ){
    this->data = nodeData;
    this->next = succ;
}
    
listNode::~listNode(){

}

// 默认构造函数
linkList::linkList() {
    firstNode = NULL;
    curNode = NULL;
    lastNode = NULL;
    listSize = 0;
}

//初始化链表
linkList::linkList(const int& size, float data[])//初始化数组长度，初始化数组
{
    firstNode = new listNode();
    curNode = firstNode;
    lastNode = firstNode;
    listSize = size;
    for (int i = 0; i < size; i++)
    {
        listNode* newNode = new listNode(data[i],NULL);
        lastNode->next = newNode;
        lastNode = newNode;
    }
    curNode = firstNode->next;
}

//销毁链表
linkList::~linkList(){
    listNode* tempNode = firstNode;
    while (tempNode != NULL) {
        listNode* nextNode = tempNode->next;
        delete tempNode;
        tempNode = nextNode;
    }
    listSize = 0;
}


//插入元素(头插法)
bool linkList::headInsertItem(const float& val)//成功返回true，失败返回false
{
    listNode* newNode = new listNode(val, NULL);
    if (newNode == NULL)
    {
        return false;
    }
    
    newNode->next = firstNode->next;
    firstNode->next = newNode;
    //如果当前结点指向头结点，则将当前结点指向新结点。
    if (curNode == firstNode) {
        curNode = newNode;
    }
    listSize ++;
    return true;
}

//插入元素(尾插法）
bool linkList::tailInsertItem(const float& val)//成功返回true，失败返回false
{
    listNode* newNode = new listNode(val, NULL);
    if (newNode == NULL)
    {
        return false;
    }
    lastNode->next = newNode;
    lastNode = newNode;
    if (curNode == firstNode) {
        curNode = newNode;
    }
    listSize++;
    return true;
}

//插入元素
int linkList::insertItem(const int& index, const float& data)//插入元素到index位置，成功返回插入位置，错误返回-1
{
    if (index < 0 or index > listSize)
    {
        return -1;
    }
    listNode* pre_node = firstNode;
    for (int i = 0; i < index; i ++)
    {
        pre_node = pre_node->next;
    }
    listNode* new_node = new listNode(data, NULL);
    new_node->next = pre_node->next;
    pre_node->next = new_node;
    //最后一个节点处插入
    if (pre_node == lastNode)
    {
        lastNode = new_node;
    }
    
    listSize ++;
    return 0;
}

//删除元素
int linkList::deleteItem(const float& val)//返回删除位置，找不到返回-1
{
    int pos = -1;
    listNode* cur_node = firstNode->next;
    listNode* pre_node = firstNode;
    while (cur_node != NULL)
    {
        pos ++;
        if (cur_node->data == val)
        {
            pre_node->next = cur_node->next;
            if (pos == this->getLength() - 1)
            {
                lastNode = pre_node;
            }
            delete cur_node;
            listSize--;
            return pos;
        }
        
        pre_node = cur_node;
        cur_node = cur_node->next;
    }
    return -1;
    
}

//查找元素（按序号找）
bool linkList::locate(const int& index, float& val)//成功返回true，值放在val中，失败返回false
{
    if (index >= listSize || index < 0)
    {
        return false;
    }
    listNode* cur_node = firstNode->next;
    for (int i = 0; i < index; i++)
    {
        cur_node = cur_node->next;
    }
    val = cur_node->data;
    return true;
}

//查找元素（按值找）
int linkList::locate(const float& val)//返回找到位置，找不到返回-1
{
    int index = -1;
    listNode* cur_node = firstNode->next;
    while (cur_node != NULL)
    {
        index ++;
        if (cur_node->data == val)
        {
            return index;
        }
        cur_node = cur_node->next;
    }
    return -1;
}

//递增排序
void linkList::ascendingOrder()
{
    listNode* p_node = firstNode->next;
    while (p_node->next != NULL)
    {
        listNode* q_node = p_node->next;
        while (q_node != NULL)
        {
            if (q_node->data < p_node->data) {
                float temp = p_node->data;
                p_node->data = q_node->data;
                q_node->data = temp;
            }
            q_node = q_node->next;
        }
        p_node = p_node->next;
    }
}

//倒排
void linkList::reverse(){
    //思路：在尾节点处依次头插法插入前面其余节点
    //或者在头节点依次头插法插入其他节点
    listNode* cur_node = firstNode->next;
    listNode* pre_node = NULL;
    while (cur_node != NULL)
    {
        listNode* next_node = cur_node->next;
        cur_node->next = pre_node;
        pre_node = cur_node;
        cur_node = next_node;
    }
    lastNode = firstNode->next;
    firstNode->next = pre_node;
    curNode = pre_node;
}


int linkList::getLength() {
    return listSize;
}

void merge(linkList& A, linkList& B){
    // 将 B 中的节点插入到 A 中
    for (int i = 0; i < B.getLength(); i++) {
        float value;
        B.locate(i, value);
        A.headInsertItem(value);
    }
    // 倒排
    A.ascendingOrder();
    A.reverse();
}
